package com.shindo.base;

/**
 * 单链表反转
 */
public class ReverseSingleLink {
    public static void main(String[] args) {
        //构建测试用例，链表指向为：N1->N2->N3->N4
        Node n4 = new Node(4, null);
        Node n3 = new Node(3, n4);
        Node n2 = new Node(2, n3);
        Node n1 = new Node(1, n2);
        Node head = n1;
        //输出测试用例
        System.out.println("原始链表指向：");
        printNode(head);

        //普通方式反转链表
        /*System.out.println("循环方式反转链表指向：");
        head = cycleNode(head);
        printNode(head);*/

        //递归方式反转链表
        System.out.println("递归方式反转链表指向为：");
        System.out.println("递归调用前，head引用指向对象：" + head.toString());
        head = recursionNode(head, null);
        System.out.println("递归调用后，head引用指向对象：" + head.toString());
        printNode(head);

    }

    /**
     * 循环打印链表数据域
     */
    private static void printNode(Node head) {
        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }
    }

    /**
     * 节点类
     * 方便后续在main方法中调用，故定义为static内部类
     */
    static class Node {
        int val; //数据域
        Node next; //指针域，指向下一个节点

        Node(int x, Node nextNode) {
            val = x;
            next = nextNode;
        }
    }

    /**
     * 循环遍历方式实现单链表反转
     */
    private static Node cycleNode(Node head) {

        Node prev = null;//保存前一个节点的信息

        //循环遍历链表中的节点
        while (head.next != null) {
            //1.先保存当前节点的下一个节点的信息到tempNext
            Node tempNext = head.next;
            //2.修改当前节点指针域，使其指向上一个节点（如果是第一次进入循环的头节点，则上一个节点为null）
            head.next = prev;
            //3.将当前节点信息保存到prev中（以做为下一次循环中第二步使用到的“上一个节点”）
            prev = head;
            //4.当前节点在之前的123步中指针域已经修改完毕，此时让head重新指向待处理的下一个节点
            head = tempNext;
        }

        //上面的循环完成后，实际只修改了原先链表中的头结点到倒数第二个节点间的节点指向反转，倒数第一个节点并未处理
        //此时prev指向原先链表中的倒数第二个节点，head指向尾节点
        //处理尾节点的指针域，使其指向前一个节点
        head.next = prev;

        //返回尾节点，此时的尾节点既是原先链表中的尾节点，又是反转后的新链表中的头结点
        return head;
    }


    private static Node recursionNode(Node head, Node prev) {
        System.out.println("递归调用中，head引用指向对象：" + head.toString());
        if (null == head.next) {
            //设定递归终止条件
            //当head.next为空时，表明已经递归到了原链表中的尾节点，此时单独处理尾节点指针域，然后递归结束。
            head.next = prev;
            System.out.println("递归调用返回前，head引用指向对象：" + head.toString());
            return head;
        }
        //1.先保存当前节点的下一个节点的信息到tempNext
        Node tempNext = head.next;
        //2.修改当前节点指针域，使其指向上一个节点(如果是第一次进入循环的头结点，则其上一个节点为null)
        head.next = prev;
        //3.将当前节点信息保存到prev中（以做为下一次递归中第二步使用到的“上一个节点”）
        prev = head;
        //4.当前节点在之前123步中指针域修改已经修改完毕，此时让head重新指向待处理的下一个节点
        head = tempNext;

        //递归处理下一个节点
        Node result = recursionNode(head, prev);
        return result;
    }

}
